C语言数据结构之二叉树的4种遍历（超详细） |
您所在的位置：网站首页 › 二叉树 有序 › C语言数据结构之二叉树的4种遍历（超详细） |
C语言数据结构之二叉树的4种遍历（超详细）
|
二叉树
代码：Tree 文章目录 二叉树树的简介树的节点子树和空树结点的度和层次有序树和无序树森林 二叉树的性质二叉树的性质满二叉树完全二叉树 二叉树的链式存储结构二叉树的遍历二叉树的先序遍历（递归与非递归）递归思想非递归思想 二叉树的中序遍历（递归与非递归）递归思想非递归思想 二叉树的后序遍历（递归与非递归）递归思想非递归思想 二叉树的层次遍历4种遍历总结 树的简介树是一种非线性的数据存储结构，而二叉树只是其中一种特殊的存储结构。 如图1：（有序二叉树）
结点：就是树结构储存的每一个元素，其可以由数据域、左孩子指针域、右孩子指针域、（父亲结点指针域）构成，如图1(B)B就是一个结点。 父结点又称双亲结点：如图1(A)、图1(B)、图1©、图1(D)、图1(G)都是父结点。 子结点、兄弟结点、堂兄结点：图1(B)、图1©都是A的子结点，而他们都有共同的父结点，所以B、C互为兄弟结点，对于在同一深度的结点而言，它们如果不是同一个父节点，那么它们互为堂兄结点。 树根结点又称根结点：每一个非空树结构都有且仅有一个根结点，如图1(A)就是这个有序二叉树的根结点。 叶子结点：如果该结点没有左孩子也没有右孩子，那么这个结点就是叶子结点，如图1(Q)、图1(I)、图1(E)、图1(F)、图1(J)都是叶子结点。 子树和空树子树：树中的每个结点都是一棵树，只不过根结点就是他本身。所以树是由根结点和若干子树构成。 空树：即构成集合为空就是空树。 对于树结构而言，有着同一个根结点的子树，不可以有着逻辑关系，不然就破坏了树的结构。如图便不再是一颗树。
度：对于一个结点而言，他有多少个子结点，便是它的度，如图1(A)它有B、C两个结点，所以它的度是2。 一棵树的度便是树内各结点度的最大值，二叉树的度为2。 结点的层次：一棵树从根结点开始，根结点为第一层，根的子结点为第二层，直到到达最深的叶子结点。如图1它的深度便是4层。 有序树和无序树有序树便是一棵树从子树从左往右数，谁在左边，谁在右边是有明确规定的，便是一棵有序树，反之则是无序树。在有序树中，一个结点最左边的子树为“第一个孩子”，最右边为“最后一个孩子“，在图1中B就是第一个孩子，C就是最后一个孩子。 森林森林是由n(n>=0)个互相不相交的树组合成的集合被称之为森林。如图1(A)的B、C两个子树构成的便是一个森林。因此树还可以是根结点和森林构成的。 二叉树的性质二叉树必须满足两个条件 本身是有序树； 整棵树的度不能大于2； 二叉树的性质 二叉树中，第n层最多有2ⁿ﹣¹个结点；如果二叉树的深度为n，二叉树最多有2ⁿ－1个结点；二叉树中，叶子结点数为n₁，度为2的结点数为n₂，则n₁=n₂+1； 满二叉树满二叉树即是除了叶子结点的其他结点度都是2的二叉树，它满足二叉树的性质还同时满足以下性质： 深度为n的满二叉树叶子结点数为2ⁿ－1；满二叉树中不存在度为1的结点，除了叶子结点度为0，其他结点度均为2.具有n个结点的满二叉树的深度为㏒₂(n+1)； 完全二叉树完全二叉树即是满二叉树除去最后一层的最后一个结点，从左往右依次分布。 完全二叉树除了满足普通二叉树的性质还同时满足以下性质： n个结点的完全二叉树深度为[㏒₂n]+1；“[ ]”取整符号当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1 。 二叉树的链式存储结构二叉树的链式存储结构是由数据域、左孩子指针域、右孩子指针域、（父亲结点指针域）构成。
二叉树遍历分为先序遍历、中序遍历、后序遍历、层次遍历共4种遍历方法，下面就逐一对其4种方法的递归与非递归实现做其阐述。 这里是先序遍历、中序遍历所用到的进栈函数、出栈函数、获取栈顶元素函数。 int top=-1;//栈顶位置 全局变量 /* 非递归遍历二叉树 进栈函数 */ void push(BiTree **a,BiTree *elem){ a[++top]=elem; } /* 非递归遍历二叉树 出栈函数 */ void pop(){ if(top==-1){ return ; } top--; } /* 非递归遍历二叉树 获取栈顶元素 */ BiTree *getTopElem(BiTree **a){ return a[top]; } 二叉树的先序遍历（递归与非递归）图2：
先序遍历的递归思想： 先访问根结点；再访问左孩子；最后访问右孩子；图2中的先序遍历递归思想： 访问根结点，找到A；访问结点A的左结点，找到B；访问结点B的左结点，找到D；由于结点D的左结点为空且又无右结点则D访问结束，返回结点B访问其右结点，找到E；由于结点E无孩子，且结点B的左右孩子均访问，则返回结点A访问其右结点，找到C；访问结点C的左结点，找到F；由于F没有子结点，则返回访问结点C的右结点，访问失败，则返回A结点，由于结点A的左右结点均访问，则这个完全二叉树的先序遍历访问结束； /* 先序遍历二叉树（递归） A B D E C F 先访问根节点，再访问左孩子，最后访问右孩子 */ void PreBiTree(BiTree *T){ if(T){ displayElem(T); PreBiTree(T->lchild); PreBiTree(T->rchild); } return ; //为空返回 } 非递归思想非递归则是使用栈的思想，将递归非递归化。 首先创建一个顺序栈；根结点A先进栈，然后出栈；如果右孩子不为空则先将右孩子压栈，再将移动指针指向左孩子，然后访问左孩子；图2中的先序遍历非递归思想： A进栈，出栈，访问A；C进栈，访问B；E进栈，访问D；D无子结点，E出栈，访问E；E无子结点，C出栈，访问C；C无右孩子，访问F； /* 先序遍历二叉树（非递归） */ void PreBiTree_Stack(BiTree *T){ BiTree *a[10]; BiTree *p=NULL; push(a,T); //根节点先进栈 while(top!=-1){ p=getTopElem(a); pop(); while(p){ displayElem(p); //栈顶不为空则展示 if(p->rchild){ push(a,p->rchild); //右孩子进栈 } p=p->lchild; //左孩子进栈 } } } 二叉树的中序遍历（递归与非递归） 递归思想中序遍历的递归思想： 先访问当前结点的左孩子；再访问根结点；最后访问当前结点的右孩子；图2中的中序遍历递归思想： 访问根结点，找到A；找到A的左孩子，B；找到B的左孩子，D；由于结点D没有左孩子则访问D；由于结点D也没有右孩子，则结点B的左子树遍历完成，访问B；找到B的右孩子，E；由于E无左子树，访问E；由于E又无右子树，则A的左子树访问完成，访问A；找到A的右孩子，C；找到C的左孩子，F；由于F没有左子树，则访问F；由于F又没有右子树，则返回访问C；由于C没有右子树，则返回A，中序遍历访问结束； /* 中序遍历二叉树（递归） D B E A F C 先访问左孩子，再访问根节点，最后访问右孩子 */ void InBiTree(BiTree *T){ if(T){ InBiTree(T->lchild); displayElem(T); InBiTree(T->rchild); } return ; //为空返回 } 非递归思想中序遍历的非递归思想： 根结点先进栈；遍历左子树让其全部压栈直到NULL，弹出NULL；弹栈，然后将父节点的右孩子压栈，再弹栈，如此反复；图2中的中序遍历非递归思想： 根结点A进栈；A的左孩子B进栈；B的左孩子D进栈；D的左孩子NULL进栈，结束循环弹出NULL；取栈顶结点D，访问D，弹栈后栈顶结点为B；访问B，B的右结点E进栈；访问E，B结点左右孩子访问结束，返回A，访问A；A的右孩子C进栈；C的左孩子F进栈；F的左孩子NULL进栈，弹出NULL；取栈顶结点F，访问F；F无左右孩子，返回C，访问C；C无右孩子，返回A，中序遍历结束； /* 中序遍历二叉树（非递归） */ void InBiTree_Stack(BiTree *T){ BiTree *a[10]; BiTree *p=NULL; push(a,T); //根节点进栈 while(top!=-1){ while((p=getTopElem(a)) && p){ push(a,p->lchild); } pop();//把左孩子的左空孩子NULL弹出 if(top!=-1){ p=getTopElem(a); displayElem(p); pop(); push(a,p->rchild);//p结点的左孩子遍历完，开始遍历右孩子 } } } 二叉树的后序遍历（递归与非递归） 递归思想后序遍历的递归思想： 先访问该结点的左孩子；再访问该节点的右孩子；最后访问该结点；图2中的后序遍历递归思路： 从根结点A开始，遍历左孩子B；遍历结点B的左孩子，找到D；由于D没有左孩子，也没有右孩子，则访问D，并返回到结点B；B的左孩子遍历完，开始遍历右孩子E，找到E；由于E没有左右孩子，则访问E，并返回到结点B；由于B结点左右孩子遍历完，则访问B，并返回到根结点A；A的左孩子遍历完，开始遍历右孩子C，找到C；遍历结点C的左孩子，找到F；由于F没有左右孩子，则访问F，并返回到结点C；C的左孩子遍历完，开始遍历右孩子，由于没有右孩子，则访问C，并返回到根结点A；A的左右孩子均遍历完成，则访问A，后序遍历结束； /* 后序遍历二叉树（递归） D E B F C A 先访问左孩子，再访问右孩子，最后访问根节点 */ void PostBiTree(BiTree *T){ if(T){ PostBiTree(T->lchild); PostBiTree(T->rchild); displayElem(T); } return ; //为空返回 } 非递归思想后序遍历的非递归思想不同于先序和中序，它需要再定义一个结构体来保存该结点的状态。 /* 后序遍历二叉树 */ typedef struct SiNode{ int state; BiTree *p; }SiNode;state=0表示该结点还没有遍历它的右孩子，state=1表示该结点为访问结点。 那么后序遍历的进栈函数、出栈函数则为 /* 后序遍历进栈函数 */ void postpush(SiNode *a,SiNode s){ a[++top]=s; } /* 非递归遍历二叉树 出栈函数 */ void pop(){ if(top==-1){ return ; } top--; }后序非递归遍历主要思路： 根结点以及左子树全部压栈，且state=0；由于栈顶为最后一个左叶子结点，取出结点以及state，弹出栈顶；如果state==0说明还没有遍历右孩子，更改其state重新压栈，遍历其右孩子；如果state!=0说明该结点左孩子右孩子都已经遍历完成，访问其结点；图2中的后序遍历非递归化思路： A、B、D结点依次入栈；取栈顶D，由于D没有左右孩子，访问D，并返回到B；由于B的state=0，则右孩子E入栈，然后修改B的state=1；由于E没有左右孩子，访问E，并返回到B；由于B的state=1，则访问B，并返回到A；由于A的state=0，则右孩子C入栈，然后修改A的state=1；C入栈后还要将其左孩子F入栈，此时栈顶结点为F；由于F没有左右孩子，访问F，并返回到C；由于C的state=0，且右孩子为NULL所以不入栈，然后修改C的state=1；由于C的state=1，则访问C，并返回到A；由于A的state=1，则访问A，此时后序遍历完成； /* 后序遍历二叉树（非递归） */ void PostBiTree_Stack(BiTree *T){ SiNode a[10]; BiTree *p=T; SiNode s; int state; while(p || top!=-1){ while(p){ s.p=p; s.state=0; postpush(a,s); p=p->lchild; } s=a[top]; pop(); p=s.p; state=s.state; if(state==0){ s.p=p; s.state=1; postpush(a,s); p=p->rchild; }else{ displayElem(p); p=NULL; } } } 二叉树的层次遍历层次遍历所需用到的是队列结构，如图2队列思路为： 根结点A入队；根结点A出队，同时将左孩子B与右孩子C分别入队；队头结点B出队，同时将左孩子D与右孩子E分别入队；队头结点C出队，同时将左孩子F入队；队头结点D出队；队头结点E出队；队头结点F出队； int front=0,rear=0;//初始化队头和尾指针 全局变量 /* 层次遍历 队列入队 */ void EnQueue(BiTree **a,BiTree *t){ a[rear++]=t; } /* 层次遍历 队列出队 */ BiTree *DeQueue(BiTree **a){ return a[front++]; } /* 层次遍历 */ void LevelBiTree_Queue(BiTree *T){ BiTree *p; BiTree *a[20]; EnQueue(a,T); while(front EnQueue(a,p->lchild); } if(p->rchild){ EnQueue(a,p->rchild); } } } 4种遍历总结
|
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |